//给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
//
//
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
//
//
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
//
//
//
// 示例 1：
//
//
//输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
//输出：4
//解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
//其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于
//n 的值 3 。
//
//
// 示例 2：
//
//
//输入：strs = ["10", "0", "1"], m = 1, n = 1
//输出：2
//解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
//
//
//
//
// 提示：
//
//
// 1 <= strs.length <= 600
// 1 <= strs[i].length <= 100
// strs[i] 仅由 '0' 和 '1' 组成
// 1 <= m, n <= 100
//
//
// Related Topics 数组与矩阵 字符串 动态规划 👍 919 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
type BinaryInfo = { numOfZero: number, numOfOne: number };
function countBinary(str: string): BinaryInfo {
    let numOfZero: number = 0,
        numOfOne: number = 0;
    for (let s of str) {
        if (s === '0') {
            numOfZero++;
        } else {
            numOfOne++;
        }
    }
    return { numOfZero, numOfOne };
}
function findMaxForm(strs: string[], m: number, n: number): number {

    /*
    1.确定dp数组（dp table）以及下标的含义
    ***dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。故dp是记录子集个数，不断更新至最大的

    2.确定递推公式
    dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
    dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。（说明0和1仍然没装满）
    然后我们在遍历的过程中，取dp[i][j]的最大值。
    所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

    3.dp数组如何初始化
    因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

    4.确定遍历顺序
    外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
     */

    const goodsNum: number = strs.length;
    const dp: number[][] = new Array(m + 1).fill(0)
        .map(_ => new Array(n + 1).fill(0));
    for (let i = 0; i < goodsNum; i++) {
        // 每次对一个物品进行时，都获取其零和1的数量
        const { numOfZero, numOfOne } = countBinary(strs[i]);
        // 这里面对0和1进行了遍历
        for (let j = m; j >= numOfZero; j--) {
            for (let k = n; k >= numOfOne; k--) {
                // 状态转移公式  谨记dp[i][j]含义：最多有i个0和j个1的strs的最大子集的*大小*为dp[i][j]。
                dp[j][k] = Math.max(dp[j][k], dp[j - numOfZero][k - numOfOne] + 1);
            }
        }
    }
    return dp[m][n];
};
//leetcode submit region end(Prohibit modification and deletion)
